n=1000;
a=[862,417,848,334,434,61,919,162,893,972,179,144,502,83,750,457,908,150,264,45,564,771,312,84,559,492,22,123,551,486,97,38,609,318,213,582,978,26,433,760,520,980,835,462,763,56,627,672,573,370,321,741,986,77,178,128,638,458,19,603,682,281,51,29,185,311,258,543,373,552,600,579,887,498,983,812,664,255,853,341,996,681,730,110,376,537,820,544,945,188,536,122,604,970,884,850,946,840,953,279,711,880,256,326,249,606,105,193,429,578,891,5,632,999,446,788,818,94,759,60,398,153,242,969,503,53,518,290,186,138,411,240,666,158,215,166,285,991,663,787,981,630,17,560,628,451,639,263,675,843,841,76,852,54,134,926,657,191,576,808,233,590,842,194,777,333,567,470,934,6,222,933,633,554,421,792,516,487,959,856,703,465,419,146,677,776,844,674,270,229,418,456,988,687,673,561,587,70,592,142,671,208,795,354,474,416,496,790,327,247,265,78,15,965,967,11,151,384,380,976,436,324,625,588,351,868,829,968,546,88,37,645,819,93,899,350,526,274,485,268,881,183,47,68,238,676,528,269,557,857,907,405,785,214,118,406,888,33,439,960,72,706,540,538,660,30,169,916,975,683,921,620,895,35,562,164,997,513,444,608,447,102,299,221,173,181,119,424,929,218,547,44,402,723,307,148,640,344,226,408,511,187,556,534,74,4,817,356,549,565,571,171,495,200,635,652,355,67,865,353,126,254,599,43,489,85,273,152,202,338,523,9,758,18,752,782,719,956,992,728,846,504,514,497,225,718,71,973,116,141,364,767,831,722,385,927,708,984,394,239,971,332,198,396,735,248,357,762,935,409,643,8,41,729,452,646,387,550,811,168,594,869,699,65,707,476,943,298,66,57,363,278,994,262,232,623,135,938,925,25,713,704,482,46,749,244,939,796,480,117,243,210,688,283,491,305,533,100,207,870,120,21,277,175,253,651,445,24,950,595,656,149,797,584,427,698,954,20,275,955,747,696,766,764,163,481,962,924,689,806,772,602,867,230,801,106,621,659,415,922,346,246,276,966,50,667,228,42,501,596,379,555,568,107,615,27,136,377,101,203,822,957,715,553,517,314,488,684,323,601,815,212,901,932,650,478,670,32,889,393,530,931,581,490,649,288,308,197,349,304,345,328,845,129,252,724,644,598,605,317,805,648,825,133,710,535,653,580,325,223,721,622,789,358,167,403,839,172,432,464,725,784,108,280,743,397,828,593,569,423,823,690,271,878,211,732,941,287,985,654,589,742,453,261,294,858,336,814,702,259,679,851,738,422,995,519,160,532,506,337,139,541,438,89,539,847,36,531,82,669,998,468,295,662,879,320,804,803,769,220,855,441,791,773,39,196,802,734,712,448,348,824,125,383,914,515,113,665,300,360,894,902,99,362,655,114,940,289,201,339,691,309,641,982,322,821,392,182,389,331,236,619,86,548,170,365,159,783,7,923,731,127,103,209,695,890,343,479,286,95,369,301,574,155,905,195,739,121,475,779,745,1000,833,216,399,958,977,407,371,461,428,964,716,124,284,473,156,386,335,898,73,140,368,292,678,484,859,794,913,912,410,374,75,510,700,205,800,875,112,507,765,993,809,472,834,16,296,466,942,388,830,827,199,237,930,529,637,81,267,147,854,206,737,570,575,477,91,634,319,467,610,770,757,780,381,241,566,401,694,111,775,542,342,726,733,431,12,413,961,204,697,90,329,642,426,367,442,522,414,499,906,611,951,658,521,282,272,250,104,692,224,109,974,161,781,949,412,143,717,727,98,352,505,347,96,636,306,293,257,629,863,904,793,165,420,917,400,832,849,989,69,631,987,40,13,586,435,838,450,910,740,471,563,63,524,761,192,483,235,359,189,378,227,909,508,1,774,176,3,500,145,572,768,297,618,756,937,577,799,816,437,231,302,810,647,545,266,493,874,313,260,882,59,28,115,340,990,361,58,184,390,459,157,661,48,705,837,963,897,612,911,826,613,245,404,720,685,469,614,798,876,860,64,936,443,813,154,494,680,872,778,23,807,219,892,372,751,52,736,375,440,463,871,80,395,668,597,616,34,896,886,87,137,583,748,624,558,31,512,291,746,686,382,877,947,920,132,786,525,903,755,2,449,62,455,979,425,864,92,527,454,873,585,315,234,190,217,948,79,626,251,49,303,754,753,915,10,310,944,430,861,836,130,180,883,55,366,709,952,744,918,131,460,607,177,900,928,391,701,617,14,885,693,509,174,330,714,866,591,316];
b=[875,555,276,284,458,225,643,369,333,440,391,723,884,668,846,634,359,87,401,809,715,235,119,654,672,157,78,616,648,856,651,878,273,182,330,11,387,554,591,622,962,534,580,18,150,824,578,135,575,698,579,468,414,45,641,269,207,32,858,630,883,437,792,376,782,23,565,27,739,346,199,22,629,222,76,423,952,179,481,980,332,428,208,542,716,819,209,610,539,63,511,748,890,733,43,586,926,968,146,463,601,40,343,349,512,897,257,764,874,184,837,382,995,134,370,464,626,175,732,445,942,194,772,752,189,650,388,833,921,312,623,59,913,24,492,712,775,128,929,533,53,508,365,364,673,598,577,389,605,123,176,425,912,584,232,2,703,553,801,187,563,137,569,816,473,794,86,66,976,904,305,412,272,302,761,99,185,173,155,434,958,133,234,867,393,750,531,644,908,334,721,212,315,868,725,159,329,224,562,693,371,275,363,836,637,558,719,793,589,474,203,144,395,490,581,426,892,174,743,854,438,15,239,210,844,104,954,108,435,728,663,932,90,31,612,436,455,948,177,204,759,692,255,183,677,471,287,549,572,169,501,861,493,488,755,245,765,75,905,781,751,165,444,594,3,620,111,849,653,448,931,503,609,778,823,660,736,834,881,394,935,140,228,124,532,688,647,41,632,608,158,592,311,362,825,956,791,320,139,68,285,344,483,316,383,314,760,141,919,162,166,516,701,535,197,386,339,848,317,509,944,160,974,244,500,396,178,263,136,353,551,504,270,615,479,138,324,48,267,850,168,607,682,186,295,206,442,424,406,88,997,308,46,29,784,661,785,28,441,839,505,116,702,635,953,466,567,188,20,163,142,400,862,480,101,418,726,544,380,392,277,452,939,288,810,55,831,604,79,34,927,624,681,690,621,251,864,524,783,754,959,37,404,181,170,254,779,118,832,96,103,109,125,180,583,576,246,889,679,538,407,258,8,410,909,740,297,190,361,636,13,381,805,69,860,201,975,461,741,525,89,631,93,808,638,894,768,390,886,415,313,453,459,642,510,171,281,711,470,568,731,417,529,130,476,573,937,243,773,356,936,658,347,97,477,666,788,820,102,928,261,427,686,827,656,990,39,938,945,306,815,560,409,338,689,796,795,800,978,219,902,552,355,443,934,348,918,756,350,485,322,491,857,674,734,402,790,33,595,957,447,499,777,218,304,342,593,216,422,526,280,200,683,680,806,67,502,618,494,770,924,233,352,151,627,366,58,253,649,985,991,420,744,722,5,368,498,153,52,215,845,853,351,372,685,696,943,880,161,299,882,221,933,303,429,152,720,522,419,992,110,786,988,71,520,126,335,986,724,973,114,236,999,888,851,213,515,230,92,328,73,373,842,293,969,379,145,489,993,44,132,36,967,300,156,737,309,9,877,652,855,454,229,753,994,198,265,486,310,10,530,714,664,4,416,262,811,143,840,478,559,984,684,375,735,557,747,457,54,57,961,291,264,62,901,706,556,195,298,286,367,757,487,742,749,247,107,787,91,659,398,885,774,403,327,496,699,112,700,814,893,460,687,331,979,513,691,625,941,231,671,336,129,738,268,340,669,838,193,131,879,279,847,70,960,202,289,172,657,61,713,450,548,717,903,639,899,676,154,127,675,82,617,430,911,729,730,1,545,100,326,360,917,7,413,645,628,602,319,12,50,122,6,891,585,727,914,307,758,587,30,378,517,240,259,946,826,519,606,695,475,966,582,704,965,708,47,98,421,507,294,266,640,514,65,377,242,910,301,547,895,117,949,982,989,972,528,766,561,646,321,710,26,611,405,432,248,841,983,80,963,876,670,105,354,707,465,227,325,597,397,278,633,780,776,662,947,214,205,828,341,550,896,865,600,763,596,223,399,541,121,323,56,35,866,678,771,449,113,543,923,16,95,859,818,148,431,164,77,115,869,167,971,746,951,812,60,357,887,852,981,745,571,220,802,374,484,798,955,523,249,241,871,411,769,283,940,252,537,922,495,799,566,762,472,705,467,446,84,667,85,916,603,106,94,385,292,822,998,613,21,238,296,872,898,1000,835,536,439,64,250,821,345,804,925,920,964,915,192,694,482,226,462,74,456,217,518,83,655,72,718,49,337,843,256,564,807,870,433,599,977,196,863,900,789,970,38,614,817,907,829,274,497,574,384,191,19,469,271,290,408,318,906,709,17,987,619,930,506,25,546,260,830,237,540,665,570,147,813,358,14,697,950,81,590,803,521,527,120,588,996,282,211,42,873,767,797,451,51,149];